<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns="http://www.w3.org/TR/REC-html40"><head>


<meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
<meta name="ProgId" content="Word.Document">
<meta name="Generator" content="Microsoft Word 9">
<meta name="Originator" content="Microsoft Word 9">
<link rel="File-List" href="http://uva.onlinejudge.org/external/106/f_files/filelist.xml">
<link rel="Edit-Time-Data" href="http://uva.onlinejudge.org/external/106/f_files/editdata.mso">
<!--[if !mso]>
<style>
v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style>
<![endif]-->
<title>Problem F - Maximum Sum II</title>
<!--[if gte mso 9]><xml>
 <o:DocumentProperties>
  <o:Author>Shahriar Manzoor</o:Author>
  <o:LastAuthor>Shahriar Manzoor</o:LastAuthor>
  <o:Revision>16</o:Revision>
  <o:TotalTime>8</o:TotalTime>
  <o:Created>2004-05-09T11:42:00Z</o:Created>
  <o:LastSaved>2004-05-24T10:43:00Z</o:LastSaved>
  <o:Pages>1</o:Pages>
  <o:Words>190</o:Words>
  <o:Characters>1087</o:Characters>
  <o:Company>ACM/ICPC</o:Company>
  <o:Lines>9</o:Lines>
  <o:Paragraphs>2</o:Paragraphs>
  <o:CharactersWithSpaces>1334</o:CharactersWithSpaces>
  <o:Version>9.2720</o:Version>
 </o:DocumentProperties>
</xml><![endif]--><!--[if gte mso 9]><xml>
 <w:WordDocument>
  <w:View>Print</w:View>
  <w:Zoom>BestFit</w:Zoom>
 </w:WordDocument>
</xml><![endif]-->
<style>
<!--
 /* Font Definitions */
@font-face
	{font-family:"Arial Unicode MS";
	mso-font-alt:Tahoma;
	mso-font-charset:128;
	mso-generic-font-family:swiss;
	mso-font-pitch:variable;
	mso-font-signature:-1 -369098753 63 0 4129023 0;}
@font-face
	{font-family:"\@Arial Unicode MS";
	mso-font-charset:128;
	mso-generic-font-family:swiss;
	mso-font-pitch:variable;
	mso-font-signature:-1 -369098753 63 0 4129023 0;}
 /* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
	{mso-style-parent:"";
	margin:0in;
	margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	font-size:12.0pt;
	font-family:"Times New Roman";
	mso-fareast-font-family:"Times New Roman";}
h1
	{mso-style-next:Normal;
	margin:0in;
	margin-bottom:.0001pt;
	text-align:justify;
	mso-pagination:widow-orphan;
	mso-outline-level:1;
	font-size:12.0pt;
	mso-bidi-font-size:10.0pt;
	font-family:"Times New Roman";
	mso-fareast-font-family:"Arial Unicode MS";
	color:black;
	mso-font-kerning:0pt;
	font-weight:normal;
	font-style:italic;}
h2
	{mso-style-next:Normal;
	margin:0in;
	margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	page-break-after:avoid;
	mso-outline-level:2;
	font-size:16.0pt;
	mso-bidi-font-size:18.0pt;
	font-family:Arial;}
h3
	{mso-style-next:Normal;
	margin:0in;
	margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	page-break-after:avoid;
	mso-outline-level:3;
	font-size:12.0pt;
	font-family:Arial;}
p.MsoCaption, li.MsoCaption, div.MsoCaption
	{mso-style-next:Normal;
	margin:0in;
	margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt;
	font-size:12.0pt;
	font-family:Arial;
	mso-fareast-font-family:"Times New Roman";
	font-weight:bold;}
p.MsoBodyText, li.MsoBodyText, div.MsoBodyText
	{margin:0in;
	margin-bottom:.0001pt;
	text-align:justify;
	mso-pagination:widow-orphan;
	font-size:12.0pt;
	font-family:"Times New Roman";
	mso-fareast-font-family:"Times New Roman";
	color:black;}
pre
	{margin:0in;
	margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	font-size:10.0pt;
	font-family:"Courier New";
	mso-fareast-font-family:"Courier New";}
@page Section1
	{size:8.5in 11.0in;
	margin:1.0in 1.25in 1.0in 1.25in;
	mso-header-margin:.5in;
	mso-footer-margin:.5in;
	mso-paper-source:0;}
div.Section1
	{page:Section1;}
-->
</style>
</head><body style="" lang="EN-US">

<div class="Section1">

<p class="MsoNormal" style="text-align: center;" align="center"><b><span style="font-size: 28pt; font-family: Arial;">Problem F</span></b><br>
<b><span style="font-size: 20pt; font-family: Arial;">Maximum
Sum II</span></b><br>
<b>Input:</b> standard input<br>
<b>Output:</b> standard output<br>
<b>Time Limit:</b> 1 second<br>
&nbsp;</p>

<p class="MsoBodyText">In a given a sequence of non-negative integers you will
have to find such a sub-sequence in it whose summation is maximum. </p>

<p class="MsoNormal" style="text-align: justify;">&nbsp;</p>

<h2>Input</h2>

<p class="MsoNormal" style="text-align: justify;">The input file contains several
input sets. The description of each set is given below:</p>

<p class="MsoNormal" style="text-align: justify;"><!--[if !supportEmptyParas]-->&nbsp;<!--[endif]--><o:p></o:p></p>

<p class="MsoNormal" style="text-align: justify;">Each set starts with an integer <b>N
(N&lt;1000)</b> that indicates how many numbers are in that set. Each of the
next <b>N</b> lines contains a single non-negative integer. All these numbers
are less than <b>10000</b>.</p>

<p class="MsoNormal" style="text-align: justify;"><!--[if !supportEmptyParas]-->&nbsp;<!--[endif]--><o:p></o:p></p>

<p class="MsoNormal" style="text-align: justify;">Input is terminated by a set
where <b>N=0</b>. This set should not be processed.</p>

<p class="MsoNormal" style="text-align: justify;">&nbsp;</p>

<h2>Output</h2>

<p class="MsoBodyText"><span style="">For each set of
input produce one line of output. This line contains one or more integers which
is are taken from the input sequence and whose summation is maximum. If there
is more than one such sub-sequence print the one that has minimum length. If
there is more than one sub-sequence of minimum length, output the one that
occurs first in the given sequence of numbers. A valid sub-sequence must have a
single number in it. Two consecutive numbers in the output are separated by a
single space.<o:p></o:p></span></p>

<p class="MsoNormal" style="text-align: justify;"><span style="color: black;"><!--[if !supportEmptyParas]-->&nbsp;<!--[endif]--><o:p></o:p></span></p>

<h1 style="text-align: left;" align="left"><b><span style="font-size: 16pt; font-family: Arial; font-style: normal;">Sample
Input<span style="">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>Output for Sample Input<o:p></o:p></span></b></h1>

<table style="border: medium none ; background: rgb(204, 204, 204) none repeat scroll 0% 0%; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial; border-collapse: collapse;" bgcolor="#cccccc" border="1" cellpadding="0" cellspacing="0">
 <tbody><tr style="">
  <td style="border: 0.5pt solid windowtext; padding: 0in 5.4pt; width: 239.4pt;" valign="top" width="319">
  <p class="MsoNormal"><b><span style="font-size: 11pt; font-family: &quot;Courier New&quot;;">2<o:p></o:p></span></b></p>
  <p class="MsoNormal"><b><span style="font-size: 11pt; font-family: &quot;Courier New&quot;;">3<o:p></o:p></span></b></p>
  <p class="MsoNormal"><b><span style="font-size: 11pt; font-family: &quot;Courier New&quot;;">4<o:p></o:p></span></b></p>
  <pre><b><span style="font-size: 11pt;">0</span></b><b><span style=""><o:p></o:p></span></b></pre></td>
  <td style="border-style: solid solid solid none; border-color: windowtext windowtext windowtext -moz-use-text-color; border-width: 0.5pt 0.5pt 0.5pt medium; padding: 0in 5.4pt; width: 222.85pt;" valign="top" width="297">
  <p class="MsoNormal" style=""><b><span style="font-size: 11pt; font-family: &quot;Courier New&quot;;">3
  4</span></b><b><span style="font-size: 11pt; color: black;"><o:p></o:p></span></b></p>
  <p class="MsoNormal" style=""><b><span style="font-size: 11pt; font-family: &quot;Courier New&quot;;">&nbsp;</span></b><b><span style="font-size: 11pt; font-family: &quot;Courier New&quot;; color: black;"><o:p></o:p></span></b></p>
  </td>
 </tr>
</tbody></table>


<div class="MsoNormal" style="text-align: center;" align="center">

<hr align="center" size="2" width="100%">

</div>


<p class="MsoCaption">Problem setter: Shahriar Manzoor, Member of Elite
Problemsetters' Panel</p>

<h3>Special Thanks: Monirul Hasan, Member of Elite Problemsetters' Panel</h3>

</div>

</body></html>